#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void heapify(int A[], int size, int index)
{
    int left = 2*index, right = 2*index+1;
    int largest = index;

    if (left <= size && A[left-1] > A[index-1]) {
	largest = left;
    }
    if (right <= size && A[right-1] > A[largest-1]) {
	largest = right;
    }

    if (largest != index) {
	swap(A[index-1], A[largest-1]);
        heapify(A, size, largest);
    }
}

void heapSort(int A[], int heapSize)
{
    for (int i =  heapSize/2; i >= 1; i--) {
	heapify(A, heapSize, i);
    }

    for (int i = heapSize-1; i >= 0; i--) {
        swap(A[0],  A[i]);
        heapSize--;
        heapify(A, heapSize, 1);
    }
    return;
}


void quickSort(int A[], int start, int end)
{
    if (start >= end) return;
    int i = start-1, j ;
     
    for (j = start; j < end; j++) {
        if (A[j] < A[end]) 
	    swap(A[++i], A[j]);
    }
    swap(A[++i], A[end]);
    quickSort(A, start, i-1);
    quickSort(A, i+1, end);
}

void merge(int A[], int start, int mid, int end)
{
    if (start == 0 && mid == 0 && end == 1)
        int test = 0;
    vector<int> first(mid-start+2, 0);
    vector<int> second(end-mid+1, 0);
    for (int i = start; i <= mid; i++)
	first[i-start] = A[i];
    first[mid-start+1] = 10000000;

    for (int i = mid+1; i <= end; i++)
	second[i-mid-1] = A[i];
    second[end-mid] = 10000000;


    int i = 0, j = 0;
    for (int k = start; k <= end; k++) {
        if (first[i] <= second[j]) A[k] = first[i++];
        else A[k] = second[j++];
    }

    return;
}

void mergeSort(int A[], int start, int end)
{
    if (start >= end) return;
    int mid = start + (end-start)/2;
    mergeSort(A, start, mid);
    mergeSort(A, mid+1, end);
    merge(A, start, mid, end);
}


int main(int argc, char **argv)
{
    int A[20], B[20], C[20];// = {2,3,7,9,12,14,56,43,65,1,5,67,65,34,32,15,16,18,32,21};
    for (int i = 0; i < 20; i++) {
	A[i] = rand()%100;
        B[i] = A[i];
        C[i] = A[i];
        cout << A[i] << " ";
    }
    cout << endl;
    
    heapSort(A, 20); 
    for (int i = 0; i < 20; i++)
        cout << A[i] << " " ;
    cout << endl;

    quickSort(B, 0, 19); 
    for (int i = 0; i < 20; i++)
        cout << B[i] << " " ;
    cout << endl;

    mergeSort(B, 0, 19); 
    for (int i = 0; i < 20; i++)
        cout << B[i] << " " ;
    cout << endl;
}
